#include <iostream>
#include <cassert>
using namespace std;
template<class T>
class List
{
	struct ListNode // 链表
	{
		T data;
		ListNode* next;
	};
private:
	ListNode* m_list; // 链表
	int m_size;
public:
	List()
	{
		m_list = new ListNode; // 头结点
		m_list->next = nullptr;
		m_size = 0;
	}
	List(T data) : List() // 委托构造 C++新特性
	{
		ListNode* node = new ListNode;
		node->data = data;
		node->next = nullptr;
		m_list->next = node;
		m_size++;
	}
	~List()
	{
		ListNode* pr = nullptr; // pr 为释放指针
		ListNode* it = m_list; // it 为迭代指针
		while (it != nullptr)
		{
			pr = it;
			it = it->next;
			delete pr;
		}
		m_list = nullptr; // 将头结点释放
		m_size = -1;
	}
public:
	void push_back(T data)
	{
		ListNode* node = new ListNode;
		node->data = data;
		node->next = nullptr;
		ListNode* current = m_list;
		while (current->next != nullptr)
		{
			current = current->next;
		}
		current->next = node;
		m_size++;
	}
	void pop_back()
	{
		if (empty())
			return;
		ListNode* pre = m_list;
		ListNode* current = m_list->next;
		while (current->next != nullptr)
		{
			current = current->next;
			pre = pre->next;
		}
		delete current;
		pre->next = nullptr;
		m_size--;
	}
	void push_front(T data)
	{
		ListNode* node = new ListNode;
		node->data = data;
		node->next = m_list->next;
		m_list->next = node;
		m_size++;
	}
	void pop_front()
	{
		if (empty())
			return;
		ListNode* current = m_list->next;
		m_list->next = current->next;
		delete current;
		m_size--;
	}
	void insert(T data, int pos)
	{
		assert(pos < m_size);
		ListNode* pre = m_list;
		for (int i = 0; i < pos; ++i)
		{
			pre = pre->next;
		}
		ListNode* node = new ListNode;
		node->data = data;
		node->next = pre->next;
		pre->next = node;
		m_size++;
	}
	void erase(T data)
	{
		if (empty())
			return;
		ListNode* pre = m_list;
		ListNode* current = m_list->next;
		while (current != nullptr && current->data != data)
		{
			current = current->next;
			pre = pre->next;
		}
		if (current == nullptr)
			return;
		pre->next = current->next;
		delete current;
		m_size--;
	}
	void eraseAll(T data)
	{
		if (empty())
			return;
		ListNode* pre = m_list;
		ListNode* current = m_list->next;
		while (current != nullptr)
		{
			while (current && current->data != data)
			{
				current = current->next;
				pre = pre->next;
			}
			if (current)
			{
				pre->next = current->next;
				delete current;
				m_size--;
				current = pre->next;
			}
		}
	}
	void clear()
	{
		ListNode* pr = nullptr; // pr 为释放指针
		ListNode* it = m_list->next; // it 为迭代指针
		while (it != nullptr)
		{
			pr = it;
			it = it->next;
			delete pr;
		}
		m_list->next = nullptr; // 未将头结点释放
		m_size = 0;
	}
public:
	bool empty()
	{
		return m_list->next == nullptr;
	}
	int size()
	{
		return m_size;
	}
	int find(T data)
	{
		ListNode* current = m_list->next;
		for (int i = 0; i < m_size; ++i)
		{
			if (current->data == data)
				return i;
			current = current->next;
		}
		return -1;
	}
	T& operator[](int pos)
	{
		assert(pos < m_size);
		ListNode* current = m_list->next;
		for (int i = 0; i < pos; ++i)
		{
			current = current->next;
		}
		return current->data;
	}
};
int main()
{
	List<int> list;
	list.push_back(1);
	list.push_back(2);
	list.push_back(3);
	list.push_back(3);
	list.push_back(3);
	list.push_back(3);
	list.push_back(3);
	list.push_back(4);
	list.push_back(5);
	list.insert(10, 2);
	list.eraseAll(3);
	list.eraseAll(3);
	list.eraseAll(3);
	list.clear();
	list.push_back(1);
	list.push_back(2);
	for (int i = 0; i < list.size(); ++i)
	{
		cout << list[i] << " ";
	}
	return 0;
}